מודל ה-RAM:

• נגדיר שפעולות מבוצעות אחת אחרי השניה, ללא פעולות מקבילות.

• כל פעולה בסיסית לוקחת זמן קבוע - יחידת זמן אחת.

• נגדיר את הפעולות הבסיסיות:

  • פעולות מתמטיות (חיבור, חיסור, כפל וחילוק).
  • השוואות (קטן, גדול, שווה, או שילוב).
  • אופרטורים בוליאנים.
  • קריאה וכתיבה לתא.
  • שליטה (תנאי if, call, return).
  • הגדרת תאים במערך.
  • איתחול תא יחיד במערך.

• דוגמא - ניתוח מיון הכנסה:

for j = 1 to A.length - 1
	key <- A[j]
	i <- j-1
	while i >= 0 and A[j] > key
		A[i+1] <- A[i]
		i <- i-1
		A[i+1] <- key

• סך הפעולות (T(n)):
• $T(n)=c_{1}n+c_2(n-1)+c_3(n-1)+c_4\sum _{j=1}^{n-1}{t}_j+c_5\sum _{j=1}^{n-1}(t_j-1)+c_6\sum _{j=1}^{n-1}(t_j-1)+c_7(n-1)$
  • המקרה הטוב ביותר:
    • הוא כאשר המערך ממוין, ובו $t_j=1$ עבור כל j.
    • זמן הריצה יהיה:
    • $(c_1+c_2+c_3+c_4+c_7)n-(c_2+c_3+c_4+c_7)=a^{\prime }n-b^{\prime }$
  • המקרה הגרוע ביותר:
    • הוא כאשר המערך ממוין הפוך , ובו $t_j=j+1$ לכל j
    • נזכור ש: $\sum _{j=1}^{n-1}=\frac{n(n+1)}{2}$ וש - $\sum _{j=1}^{n-1}=\frac{n(n-1)}{2}$
    • זמן הריצה יהיה:

- הערה: ניתוח האלגוריתמים הוא לא תלוי מחשב ומתעלם מהחומר אלא כמספר הפעולות האלמנטריות המבוצעות.

ריצה בשאיפה לאינסוף:

• ניתוח זמן ריצה הוא אסימפטוטי, משמע מה זמן הריצה כתלות בקלט כאשר הקלט הוא n וגדל.

• לכן, בשאיפה לאינסוף נוכל בביטויים מסוג $a{n}^2+bn+c$ נוכל להזניח את bn ואת c ביחס ל $a{n}^2$

• סימון big O:

  • נקרא גם חסם עליון
  • משפחת O(g) הן משפחה של פונקציות שכולן גדלות כמו או פחות מ - g בשאיפה לאינסוף.
  • פורמלית: פונקציה f היא חלק מהמשפחה אם קיימים קבועים חיוביים $c,n_0$ כך ש:
  • $cg(n)\ge f(n)\ge 0foralln\ge n_0$
  • כלומר, g גדול מ - f עד כדי הכפלה בקבוע החל ממקום מסוים.
  • 
  • לדוגמא:
    • $2n^2+3n\in O(n^2)$
    • $0\le 2n^2+3n\le c{n}^2$
    • ניתן לראות שהביטוי גדול מאפס.
    • $2n^2+3n\le 2n^2+3n^2=5n^2$
    • מכאן, שהתנאי מתקיים עבור $c=5$ ו $n_0=1$

• סימון $\mathrm{\Omega }$ :

  • נקרא גם חסם תחתון.
  • משפחת $\mathrm{\Omega }(g)$ היא משפחת כל הפונקציות שגדלות לפחות באותה מהירות של g כאשר n מתקרב לאינסוף
  • פורמלית: פונקציה f היא חלק מהמשפחה אם קיימים קבועים חיוביים $c,n_0$ כך ש:
    • $f(n)\ge cg(n)\ge 0foralln\ge n_0$
    • כלומר, g קטנה מ f עד כדי הכפלה בקבוע החל ממקום מסוים.
  • 
  • לדוגמא:
    • $\frac{1}{2}{n}^2-3n\in \mathrm{\Omega }(n^2)$
    • $0\le c{n}^2\le \frac{1}{2}{n}^2-3n$
    • $c{n}^2\le \frac{1}{2}{n}^2-3n⟺3n\le (\frac{1}{2}-c)n^2⟺\frac{3}{\frac{1}{2}-c}\le n$
    • מכאן, ניתן לראות שהתנאי מתקיים עבור $c=\frac{1}{4}$ ועבור $n_0=12$

• סימון $\mathrm{\Theta }(g)$:

  • נקרא גם חסם הדוק.
  • משפחת כל הפונקציות שגדול כמו g כאשר n שואף לאינסוף.
  • $\mathrm{\Theta }(g)=O(g)\cap \mathrm{\Omega }(g)$
  • פורמלית: פונקציה f היא חלק מהמשפחה אם קיימים קבועים $c_1,c_2,n_0$ כך ש:
  • $c_{2}g(n)\ge f(n)\ge cg(n)\ge 0foralln\ge n_0$
  • כלומר, פונקציה יחיד g חוסמת את f מלמעלה ומלמטה עד כדי הכפלה בקבוע החל ממקום מסוים.
  • 

• אינוטאיציות בסימונים אסימפטוטים:

  • מיקום במשוואה:
    • סימון בצד ימין של המשוואה משמע חלק מהמשפחה שלה.
      • לדוגמא: $n=O(n^2)\to n\in O(n^2)$
    • סימון בצד ימין משמעו פונקציה אנונימית כלשהיא.
      • לדוגמא: $2n^2+3n+1=2n^2+\mathrm{\Theta }(n)\to 2n^2+3n+1=2n^2+f(n)forf(n)\in \mathrm{\Theta }(n)$
    • סימון בצד שמאל משמעו גם כן פונקציה אנונימת כלשהיא.
      • לדוגמא: $2n^2+\mathrm{\Theta }(n)=\mathrm{\Theta }(n^2)$ משמעו שלכל פונקציה g(n) ב $\mathrm{\Theta }(n)$ קיימת פונקציה f(n) ב $\mathrm{\Theta }(n^2)$ כך שמתקיים: $2n^2+g(n)=f(n)$
  • התנהגויות:
    • סימון O מתנהג כמו חסם עליון ($\le$)
    • סימון $\mathrm{\Omega }$ מתנהג כמו חסם תחתון ($\ge$)
    • סימון $\mathrm{\Theta }$ מתנהג כמו חסם הדוק (=)
  • ישנן פונקציות שאי אפשר להשוות ביניהן
  • תכונות:
    • טרנזטיביות:
      • $f\in \mathrm{\Theta }(g)andg\in \mathrm{\Theta }(h)impliesf\in \mathrm{\Theta }(h)$
      • $sameforO,\mathrm{\Theta }$
    • רפלקסיביות:
      • $f\in \mathrm{\Theta }(f)$
      • $sameforO,\mathrm{\Theta }$
    • סימטריה:
      • $f\in \mathrm{\Theta }(g)\leftrightarrow g\in \mathrm{\Theta }(f)$
    • טרנספוז סימטרי:
      • $f\in O(g)\leftrightarrow g\in \mathrm{\Omega }(f)$

נוסחאות נסיגה:

• נסיגה היא שיוויון או אי שיוויון של פונקציה שערכיה משתמשים בפונקציה אך עם קלט קטן יותר (סוג של רקורסיה).

• לדוגמא:

$T(n)=\{\begin{array}{ll}1& \text{if }n=1\\ T(n-1)+1& \text{if }n>1\end{array}$

• דרכים לפתור נוסחאות נסיגה:
  • שיטת הניחוש:
    • בשיטה זו מנחשים את הפתרון של נוסחאת הנסיגה ואז מוכיחים את הנכונות באינדוקציה.
    • לדוגמא:
      • הנסיגה: $T(n)=\{\begin{array}{ll}1& \text{if }n=1\\ 2T(n/2)+n& \text{if }n>1\end{array}(n\text{ is a power of 2})$
      • הניחוש: $T(n)=n\log n+n$
      • צעד הבסיס: $n=1,n\log n+n=1=T(1)$
      • צעד האינדוקציה: $$
        \begin{gathered}
        \text{Assume } T(m) = m \log m + m \text{ for all } m < n. \[15pt]

\begin{aligned}
T(n) &= 2T(n/2) + n \
&= 2\left(\frac{n}{2} \log \frac{n}{2} + \frac{n}{2}\right) + n \quad \text{(by the induction hypothesis)} \
&= n \log \frac{n}{2} + n + n \
&= n \log n - n \log 2 + n + n \
&= n \log n - n + n + n \
&= n \log n + n
\end{aligned}
\end

\begin{gathered}
\begin{aligned}
T(n) &= T(n-1) + n \
&= T(n-2) + (n-1) + n \
&= T(n-3) + (n-2) + (n-1) + n \
&\quad \vdots \
&= T(n-k) + (n-k+1) + (n-k+2) + \dots + n \
&\quad \text{(proved using induction)} \
&= 1 + 2 + \dots + n \quad (\text{take } k = n - 1) \[10pt]
&= \frac{n(n+1)}{2}
\end{aligned}
\end

\begin{gathered}
T(n) = \begin{cases}
1 & \text{if } n = 1 \
T(n-1) + n & \text{if } n > 1
\end{cases} \[25pt]

T_2(n) = \begin{cases}
\color{red}{2} & \text{if } n = 1 \
T_2(n-1) + \color{red}{n + 2\sqrt{n}} & \text{if } n > 1
\end{cases} \[25pt]
\end

\begin{gathered}
\begin{aligned}
T_2(n) &= T_2(n-1) + n + 2\sqrt{n} \
&\overset{\text{i.h.}}{\leq} 3T(n-1) + n + 2\sqrt{n} \
&\leq 3T(n-1) + 3n \
&= 3T(n).
\end{aligned} \[25pt]
\end